<head>
    <meta charset="UTF-8">
<title>算法训练 Berland Traffic</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <div>【问题描述】</div>
<div>现有一个n个点m条边的网络。每条边有一个容量限制，对于一条边&lt;x,y&gt;，设其流量为t，容量为c，如果t大于0则是从x流向y，反之就是从y流向x，但t的绝对值不能超过c且可以不是整数。网络中节点1是源点，节点n是汇点，对于除1,n外的所有点，流入的流量等于流出的流量。这个网络有一个奇怪的性质，对于任意一对节点(x,y)，x到y的路径上流量之和不会随着选择不同的路径而改变（有可能有小于0的流量，流量的符号取决于x到y路径上这条边的方向）。</div>
<div>求满足上述条件且流过该网络的流量尽可能大的方案以及最大的流量是多少。</div>
<div>&nbsp;</div>
<div>【输入格式】</div>
<div>第一行包含两个正整数n,m。</div>
<div>接下来有m行，每行3个整数a_i,b_i,c_i，描述一条边，分别表示连接的两个端点和这条边的容量限制。</div>
<div>&nbsp;</div>
<div>【输出格式】</div>
<div>第一行输出最大的通过该网络的流量的值。</div>
<div>接下来m行，分别表示每条边的流量，顺序和输入一致。</div>
<div>至少需要保留到小数点后五位。</div>
<div>&nbsp;</div>
<div>【样例输入】</div>
<div>2</div>
<div>3</div>
<div>1 2 2</div>
<div>1 2 4</div>
<div>2 1 1000</div>
<div>&nbsp;</div>
<div>【样例输出】</div>
<div>6.00000</div>
<div>2.00000</div>
<div>2.00000</div>
<div>-2.00000</div>
<div>&nbsp;</div>
<div>【数据规模与约定】</div>
<div>n&lt;=100, m&lt;=5000</div>
<div>1&lt;=a_i,b_i&lt;=n, c_i&lt;=10000</div>
<div>&nbsp;</div>